package com.mgq.algorithm.link;

/**
 * @author MaGuangQi
 * 检测链表环相交的第一个节点
 * @date 2021-12-31 16:58
 **/
public class DetectCycle_142 {

    public ListNode detectCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while (fast != null && fast.next != null) {
            slow=slow.next;
            fast=fast.next.next;
            //有环
            if (slow == fast) {
                break;
            }
        }
        //有可能没进if,但是没有环
        if (fast == null||fast.next==null) {
            return null;
        }
        //慢指针从头开始
        slow=head;
        while (slow != fast) {
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}
